package com.test.daily.leetcode.y2022.m05.day0518.v05;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/18 下午 01:29
 * @version: 1.0
 */
public class Solution {
    // 來到了前綴樹
    public static class Node{
        public int pass;
        public int end;
        public Node[] nexts;
        public Node(){
            this.nexts = new Node[26];
        }
    }
    public static class TrieTree{
        public Node root;
        public TrieTree(){
            root = new Node();
        }
        public void insert(String s){
            if(s==null || s.length() <1){
                return;
            }
            char[] str = s.toCharArray();
            Node node = root;
            node.pass++;
            for (int i = 0; i < str.length; i++) {
                int index = str[i] - 'a';
                if(node.nexts[index] == null){
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end++;
        }
        public int search(String s){
            if(s == null || s.length() < 1){
                return 0;
            }
            char[] str = s.toCharArray();
            Node node = root;
            for(int i = 0; i < str.length; i++){
                int index = str[i] - 'a';
                if(node.nexts[index] == null){
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }
        public void delete(String s){
            if(s == null || s.length() < 1){
                return;
            }
            if(search(s) > 0){
                Node node = root;
                node.pass--;
                char[] str = s.toCharArray();
                for(int i = 0; i < str.length; i++){
                    int index = str[i] - 'a';
                    if(--node.nexts[index].pass == 0){
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }
        public int prefixNumber(String s){
            if(s == null || s.length() < 1){
                return 0;
            }
            char[] str = s.toCharArray();
            Node node = root;
            for (int i = 0; i < str.length; i++) {
                int index = str[i] - 'a';
                if(node.nexts[index] == null){
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }
}
